Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret, without which it is infeasible if not nearly impossible to break the scheme. Although the secret information is generally stored within a secure boundary in a cryptographic processor, which makes it difficult for an attacker to get at it directly, various schemes or attacks are known that attempt to obtain the secret information. A well known attack is a timing or “side channel attack”, which exploits some implementation aspect of a cryptographic algorithm such as the sequential computational operations.
For example, group operations, called multiplication modulo n in RSA schemes, and addition of points in Elliptic Curve (EC) schemes are sequentially repeated in a particular way to perform a scalar operation. In RSA, the operand is an exponent, the operation is exponentiation, and a method of multiplying is commonly known as repeated “square-and-multiply”. In EC, the operand is a scalar, the operation is a scalar multiplication of a point, and a method of multiplying is known as “double-and-add”. Both methods are well known in the art and thus further details need not be discussed.
Many techniques have been employed to ascertain a private key using power analysis. For example, careful analysis of an end-to-end waveform can decompose the order of double-and-add or square-and-multiply operations. Using the standard algorithms, either a double or a square occurs for each bit of either the exponent or scalar multiplier respectively and an “add” occurs where the bit is a notional ‘1’. Therefore, the instances where double waveforms are adjacent each other represent bit positions with zeros and for add waveforms this indicate bits with a one. These timing measurements can thus be analysed by an attacker to find the entire secret key and compromise the cryptographic system.
In addition to square-and-multiply and double-and-add techniques, other methods to compute a point multiple such as kP or a modular exponentiation such as ge use, for example, the well known “binary ladder” or Montgomery method. Using this method for EC operations, the x-coordinates of the pair of points (kiP, (ki+1)P) are computed. The Montgomery method is an efficient algorithm for performing moduli multiplication, illustrated by the following example.
Given a group E(Fp) and given a point P on the elliptic curve, the Montgomery method may be used to compute another point kP which is a scalar multiple of the point P. Given an ordered pair of points (kiP, (ki+1)P), for each bit of the binary representation of k, if the bit is a zero then the next set of points is computed by doubling the previous first point to obtain the first point in the next pair, and adding a one to this result to form the second point in the next pair, namely: (2kiP, (2ki+1)P). If the bit is a one, then the next set of points is computed by adding the previous points together to form the first point in the next pair, and adding a one to this result to form the second point in the next pair, namely: ((2ki+1)P, (2ki+2)P). It can be seen that the first point of the next pair is derived from a doubling or adding operation depending on whether the bit is a 0 or 1. In an RSA scheme, The Montgomery method is used for exponentiation, where the ordered pair of points is (ge, ge+1).
In a cryptographic processor, each of the double and adds or square and multiplies involve multiple operations which generate unique power signatures. By observing these power signatures the attacker may derive a sequence of zeros and ones and thus the scalar or exponent being used. The Montgomery method however is preferable in EC cryptographic (ECC) systems because of its extreme efficiency over the standard double-and-add.
As described in U.S. Pat. No. 6,738,478 to Vanstone et al. issued May 18, 2004, a scheme is presented where the double and add operations are performed consistently in Montgomery operations to produce a consistent power signature waveform and thus provide little information to a potential attacker. This improved scheme operates as follows, while examining the bits of the scalar. If the bit is a zero, the first element of the input pair (a, b) is doubled and stored in the first element of the output pair (a′, b′), while the first and second elements of the input are added (i.e. a+b) and placed in the second element b′ of the output pair (a′, b′). If the bit is a one, the second element b of the input pair is doubled and stored in the second element of the output pair (a′, b′), while the first and second elements are added and placed in the first element of the output pair (a′, b′). These steps are repeated for all bits of the scalar k. By performing the doubling operation, followed by the add operation for each bit, regardless of whether the bit is a one or zero, the operations are consistent for each bit.
Although the uniformity of the improved Montgomery method described above is useful in protecting the system from side channel attacks, it does not address or provide protection against fault injection. This is because fault injection attacks are active and do not necessarily rely on the observation of the timing or power consumption of certain operations. As such, a fault injection attack can be successful despite efforts to guard against side-channel attacks. Fault injection is a technique where errors are introduced into a cryptographic module in some way, in hope that erroneous results might reveal some secret keying information. Such faults can for example be induced by clock glitches, power glitches or by changing the temperature of the environment.
Fault injection attacks can be provisional (transient or reversible) or destructive (permanent). In either case, if performed during a cryptographic operation, one or more of the cryptographic computations may be altered in a specific way to possibly reveal details of a secret value. In the case of a Montgomery ladder, for example, an attacker may be interested in injecting a fault in to the binary ladder operations to reveal the random value k that is used as a private key.
It is therefore an object of the following to provide a method and apparatus for performing fault detection in cryptographic operations, in particular during exponentiation and point multiplication.